package mr.go.set;

import java.util.*;
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

/**
 * 
 * <p>
 * <tt>AggregatedSet</tt> has all Java's {@link Set} semantics. Additionally, it
 * associates a value with every element. Every AggregatedSet operates on these
 * value using {@link Aggregator aggregator}, which provides inital value for
 * newly added element, and method to produce value for existing element
 * (combining actual value and provided value). Set elements can be iterated
 * over using values' natural ordering (if they implement {@link Comparable}),
 * or ordering imposed by {@link Comparator} passed either in constructor or
 * {@link AggregatedSet#makeView(AggregatedSet, Comparator) makeView} method,
 * depending on how set was created
 * </p>
 * 
 * <p>
 * Single element operations: checking for presence, obtaining current value,
 * insertions, deletions and removals should be performed in constant time.
 * Collection-based operations are to be executed in linear time with respect to
 * size of collection. Predicate-based operations which return collection of
 * elements are to be executed in linear time with respect to size of set.
 * Predicate-based operations which return boolean values should be executed in
 * constant time. To meet these guarantees <tt>AggregatedSet</tt> is not
 * maintaining its members ordering during any operations. Elements are copied
 * and sorted only for purpose of iteration, if needed. Therefore, it may be too
 * expensive to use this set if ordered iterations are going to be frequent. The
 * best performance is achieved in scenario when majority of operations are
 * set-operations and iterations are relatively rare
 * </p>
 * 
 * <p>
 * This implementation is thread-safe. Many threads are allowed to access this
 * set without need for external synchronization. It uses only lightweight,
 * lock-free synchronization primitives. Single element value is guaranteed to
 * be changed atomically. Getting element's value is atomic with respect to
 * updates, as well.
 * </p>
 * 
 * <p>
 * All {@link AggregatedSet#makeView(AggregatedSet, Comparator) views} created
 * from a set are backed by it. This relation is transitive. That means that
 * they reflect all changes that have been made to the original set since they
 * were created, and vice versa, all modifying operations on views are reflected
 * in the set they originate from.
 * </p>
 * 
 * @author Marcin Rzeźnicki
 * 
 * @param <E>
 *            type of element this set will hold
 * @param <P>
 *            type of elements' values
 * @see Aggregator
 * 
 */
public class AggregatedSet<E, P> extends AbstractSet<E> {

	/**
	 * Creates {@code set} view. View is backed by {@code set}, so any changes
	 * made to either one are reflected in the other. This method gives its
	 * client possibility to specify different ordering of set's values.
	 * 
	 * @param <E>
	 *            type of elements in {@code set}
	 * @param <P>
	 *            type of elements' values in {@code set}
	 * @param set
	 *            set which view is taken
	 * @param comp
	 *            comparator imposing values ordering in new set (if null
	 *            natural ordering is used)
	 * @return new set backed by {@code set}
	 */
	public static <E, P> AggregatedSet<E, P> makeView(
			AggregatedSet<? extends E, ? extends P> set,
			Comparator<P> comp) {
		return new AggregatedSet<E, P>(set, comp);
	}

	/**
	 * Sorts an array <i>in situ</i> using Shell's algorithm (actually, if array
	 * is big in size it uses quick-sort instead)
	 * 
	 * @param <T>
	 *            type of elements in {@code array}
	 * @param array
	 *            array to be sorted
	 */
	public static <T extends Comparable<? super T>> void shellsort(T[] array) {
		if (array.length >= SEDGEWICKS_INCS[0]) {
			Arrays.sort(array); // for larger n's this call should be faster
			return;
		}
		int i, j, h;
		Comparable<? super T> elem;
		for (int k = 0; k < SEDGEWICKS_INCS.length; k++) {
			for (h = SEDGEWICKS_INCS[k], i = h; i < array.length; i++) {
				elem = array[i];
				j = i;
				while (j >= h && elem.compareTo(array[j - h]) < 0) {
					array[j] = array[j - h];
					j -= h;
				}
				array[j] = (T) elem;
			}
		}
	}

	/**
	 * * Sorts an array <i>in situ</i> using Shell's algorithm (actually, if
	 * array is big in size it uses quick-sort instead). Elements of {@code
	 * array} are compared using provided comparator
	 * 
	 * @param <T>
	 *            type of elements in {@code array}
	 * @param array
	 *            array to be sorted
	 * @param comparator
	 *            comparator to be used
	 */
	public static <T> void shellsort(T[] array, Comparator<? super T> comparator) {
		if (array.length >= SEDGEWICKS_INCS[0]) {
			Arrays.sort(array); // for larger n's this call should be faster
			return;
		}
		int i, j, h;
		T elem;
		for (int k = 0; k < SEDGEWICKS_INCS.length; k++) {
			for (h = SEDGEWICKS_INCS[k], i = h; i < array.length; i++) {
				elem = array[i];
				j = i;
				while (j >= h && comparator.compare(elem, array[j - h]) < 0) {
					array[j] = array[j - h];
					j -= h;
				}
				array[j] = elem;
			}
		}
	}

	protected final Aggregator<P>			aggregator;

	protected final HashMap<E, Value<P, E>>	backingSet;

	protected final Comparator<P>			comparator;

	protected final Lock					r;

	protected final ValueComparator			valueComparator;

	protected final Lock					w;

	private final ReentrantReadWriteLock	lock	= new ReentrantReadWriteLock();

	private volatile int					size;

	/**
	 * Create new set with given aggregator. Values must be comparable between
	 * each other if this constructor is used
	 * 
	 * @param a
	 *            aggregator
	 */
	public AggregatedSet(
			Aggregator<P> a) {
		this(a, null);
	}

	/**
	 * Creates new set with give aggregator. {@code comp} will be used for
	 * sorting values
	 * 
	 * @param a
	 *            aggregator
	 * @param comp
	 *            comparator
	 */
	public AggregatedSet(
			Aggregator<P> a,
			Comparator<P> comp) {
		backingSet = new HashMap<E, Value<P, E>>();
		aggregator = a;
		comparator = comp;
		if (comparator != null)
			valueComparator = new ValueComparator();
		else
			valueComparator = null;
		r = lock.readLock();
		w = lock.writeLock();
	}

	/**
	 * Creates new set. Populates with elements of {@code c}. If {@code c}
	 * contains unique elements, every element in aggregated set will have its
	 * {@link Aggregator#initial() initial value}. Otherwise, only unique
	 * elements will have its initial value. Value of any repeated element will
	 * be calculated using {@code a} as follows: first instance of element will
	 * be given its initial value, every next instance (in order of appearance
	 * in {@code c}) of this element will be given value produced by
	 * {@link Aggregator#aggregate(Object, Object)} with null passed as its
	 * first argument and current value passed as second
	 * 
	 * @param c
	 *            collection of elements to be placed in new set
	 * @param a
	 *            aggregator
	 */
	public AggregatedSet(
			Collection<? extends E> c,
			Aggregator<P> a) {
		this(c, a, null);
	}

	/**
	 * Creates new set. Populates with elements of {@code c}. If {@code c}
	 * contains unique elements, every element in aggregated set will have its
	 * {@link Aggregator#initial() initial value}. Otherwise, only unique
	 * elements will have its initial value. Value of any repeated element will
	 * be calculated using {@code a} as follows: first instance of element will
	 * be given its initial value, every next instance (in order of appearance
	 * in {@code c}) of this element will be given value produced by
	 * {@link Aggregator#aggregate(Object, Object)} with null passed as its
	 * first argument and current value passed as second
	 * 
	 * @param c
	 *            collection of elements to be placed in new set
	 * @param a
	 *            aggregator
	 * @param comp
	 *            comparator
	 */
	public AggregatedSet(
			Collection<? extends E> c,
			Aggregator<P> a,
			Comparator<P> comp) {
		this(c.size(), a, comp);
		P initialValue = a.initial();
		for (E e : c) {
			if (!backingSet.containsKey(e)) {
				final Value<P, E> value = new Value<P, E>(initialValue, e);
				backingSet.put(e, value);
			} else {
				final Value<P, E> value = backingSet.get(e);
				backingSet.put(e, new Value<P, E>(aggregator.aggregate(
						null,
						value.getValue()), e));
			}
		}
		size = backingSet.size();
	}

	/**
	 * The same as {@link AggregatedSet#AggregatedSet(Aggregator)}, only that
	 * new instance will have preallocated capacity
	 * 
	 * @param initialCapacity
	 * @param a
	 */
	public AggregatedSet(
			int initialCapacity,
			Aggregator<P> a) {
		this(initialCapacity, a, null);
	}

	/**
	 * The same as
	 * {@link AggregatedSet#AggregatedSet(int, Aggregator, Comparator)}, only
	 * that new instance will have preallocated capacity
	 * 
	 * @param initialCapacity
	 * @param a
	 * @param comp
	 */
	public AggregatedSet(
			int initialCapacity,
			Aggregator<P> a,
			Comparator<P> comp) {
		backingSet = new HashMap<E, Value<P, E>>(initialCapacity);
		aggregator = a;
		comparator = comp;
		if (comparator != null)
			valueComparator = new ValueComparator();
		else
			valueComparator = null;
		r = lock.readLock();
		w = lock.writeLock();
	}

	/**
	 * 
	 * @param c
	 *            set which: backing set, aggregator, locks are used in newly
	 *            created instance
	 * @param comp
	 *            comparator
	 */
	@SuppressWarnings("unchecked")
	protected AggregatedSet(
			AggregatedSet<? extends E, ? extends P> c,
			Comparator<P> comp) {
		backingSet = (HashMap) c.backingSet;
		aggregator = (Aggregator<P>) c.aggregator;
		comparator = comp;
		if (comparator != null)
			valueComparator = new ValueComparator();
		else
			valueComparator = null;
		r = c.r;
		w = c.w;
		size = c.size;
	}

	/**
	 * {@inheritDoc}. Element will have {@link Aggregator#initial() initial
	 * value}
	 * 
	 * @see AbstractSet#add(Object)
	 * @category set operation
	 */
	@Override
	public boolean add(E e) {
		boolean elementExists;
		r.lock();
		Value<P, E> elementValue = backingSet.get(e);
		r.unlock();
		elementExists = elementValue != null;
		if (elementExists) {
			atomicUpdate(elementValue);
		} else {
			w.lock();
			try {
				elementExists = writeElementUnsafe(e);
			} finally {
				w.unlock();
			}

		}
		return !elementExists;
	}

	/**
	 * Adds element to set with given value. If element did not exist in set it
	 * is added with {@code value} as inital value, if it did, value is produced
	 * using {@link Aggregator#aggregate(Object, Object) aggregator}
	 * 
	 * @category set operation
	 * @param e
	 *            elemnt to add
	 * @param value
	 *            initial or next value
	 * @return whether element is new
	 * @see AggregatedSet#add(Object)
	 */
	public boolean add(E e, P value) {
		boolean elementExists;
		r.lock();
		Value<P, E> elementValue = backingSet.get(e);
		r.unlock();
		elementExists = elementValue != null;
		if (elementExists) {
			atomicUpdate(elementValue, value);
		} else {
			w.lock();
			try {
				elementExists = writeElementUnsafe(e, value);
			} finally {
				w.unlock();
			}

		}
		return !elementExists;
	}

	/**
	 * Returns collection of elements satisfying {@link Predicate predicate}.
	 * Elements in this collection had value satysfying
	 * {@link Predicate#evaluate(Object) condition} at the time of check. Please
	 * keep in mind that they may have been modified since
	 * 
	 * @category predicate operation
	 * @param condition
	 *            predicate to evaluate on each value
	 * @return collection of elements satisfying {@code condition}
	 */
	public Collection<E> allSatisfying(Predicate<P> condition) {
		r.lock();
		try {
			return checkConditionUnsafe(condition);
		} finally {
			r.unlock();
		}
	}

	/**
	 * Returns collection of elements satisfying {@link Predicate predicate}.
	 * Elements in this collection had value satysfying
	 * {@link Predicate#evaluate(Object) condition} when this method returns.
	 * Please keep in mind that they may have been modified since. This method
	 * is <tt>strict</tt>, so it blocks the set for updates while it executes.
	 * It may be useful if you want to know what elements match {@code
	 * condition} precisely during this method execution
	 * 
	 * @category predicate operation
	 * @param condition
	 *            predicate to evaluate on each value
	 * @return collection of elements satisfying {@code condition}
	 */
	public Collection<E> allSatisfyingStrict(Predicate<P> condition) {
		w.lock();
		try {
			return checkConditionUnsafe(condition);
		} finally {
			w.unlock();
		}
	}

	@Override
	public void clear() {
		w.lock();
		backingSet.clear();
		size = 0;
		w.unlock();
	}

	/**
	 * Iterates over this set's <tt>snapshot</tt> in order imposed by this set
	 * <tt>comparator</tt>
	 * 
	 * @category ordered iteration operation
	 * @return consuming iterator - it removes from the set every element
	 *         returned by its {@link Iterator#next() next} method. All elements
	 *         not iterated over are left untouched
	 */
	public ValueIterator<E, P> consume() {
		return new ConsumingIterator();
	}

	@Override
	public boolean contains(Object o) {
		boolean elementExists;
		r.lock();
		elementExists = backingSet.containsKey(o);
		r.unlock();
		return elementExists;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		boolean modified;
		r.lock();
		modified = backingSet.keySet().containsAll(c);
		r.unlock();
		return modified;
	}

	/**
	 * Returns atomically value associated with {@code e}
	 * 
	 * @param e
	 *            element
	 * @return value of element or null if {@code e} not present in the set
	 */
	public P getCurrentValue(E e) {
		P value;
		r.lock();
		Value<P, E> elementValue = backingSet.get(e);
		r.unlock();
		if (elementValue != null) {
			value = elementValue.getValue();
		} else {
			value = null;
		}
		return value;
	}

	/**
	 * {@inheritDoc}
	 * 
	 * This iterator is unordered. Iterates over this set's <tt>snapshot</tt>
	 */
	@Override
	public Iterator<E> iterator() {
		return new BasicIterator();
	}

	/**
	 * Iterates over this set's <tt>snapshot</tt> in reverse order imposed by
	 * this set <tt>comparator</tt>
	 * 
	 * @category ordered iteration operation
	 * @return consuming iterator - it removes from the set every element
	 *         returned by its {@link Iterator#next() next} method. All elements
	 *         not iterated over are left untouched
	 * @see #consume()
	 */
	public ValueIterator<E, P> rconsume() {
		return new ConsumingDescendingIterator();
	}

	@Override
	public boolean remove(Object o) {
		boolean elementExists;
		Value<P, E> value;
		w.lock();
		value = backingSet.remove(o);
		size = backingSet.size();
		w.unlock();
		elementExists = value != null;
		return elementExists;
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		boolean modified;
		w.lock();
		modified = backingSet.keySet().removeAll(c);
		size = backingSet.size();
		w.unlock();
		return modified;
	}

	/**
	 * As {@link #removeAll(Collection)} but additionaly checks whether value of
	 * element in {@code c} is satisfying {@code condition} at the time of
	 * check. It does not guarantee that removed elements will not be present in
	 * the set when this method returns. They may have been placed again by
	 * another concurrent operation (with their initial values)
	 * 
	 * @category predicate operation
	 * @param c
	 * @param condition
	 * @return whether set has been modified by this method
	 * @see #removeIf(Object, Predicate)
	 */
	public boolean removeAllIf(Collection<? extends E> c, Predicate<P> condition) {
		boolean modified = false;
		for (E e : c) {
			modified |= removeIf(e, condition);
		}
		return modified;
	}

	/**
	 * As {@link #removeAll(Collection)} but additionaly checks whether value of
	 * element in {@code c} is satisfying {@code condition}. This method is
	 * <tt>strict</tt>, so it blocks the set for updates while it executes.
	 * 
	 * @category predicate operation
	 * @param c
	 * @param condition
	 * @return whether set has been modified by this method
	 * @see #removeAllIf(Collection, Predicate)
	 */
	public boolean removeAllIfStrict(
			Collection<? extends E> c,
			Predicate<P> condition) {
		boolean modified = false;
		Value<P, E> elementValue;
		w.lock();
		try {
			for (E e : c) {
				elementValue = backingSet.get(e);
				if (elementValue != null
					&& condition.evaluate(elementValue.getValue())) {
					modified = true;
					backingSet.remove(e);
				}
			}
			size = backingSet.size();
		} finally {
			w.unlock();
		}
		return modified;
	}

	/**
	 * Removes all elements of set which values satisfy {@code condition} during
	 * the time of check
	 * 
	 * @category predicate operation
	 * @param condition
	 *            condition to check elements' values against
	 * @return collection of removed elements
	 */
	public Collection<E> removeAllSatisfying(Predicate<P> condition) {
		Collection<E> result = allSatisfying(condition);
		if (!result.isEmpty())
			removeAll(result);
		return result;
	}

	/**
	 * Removes all elements of set which values satisfy {@code condition}. This
	 * method is <tt>strict</tt>, so it blocks the set for updates while it
	 * executes.
	 * 
	 * @category predicate operation
	 * @param condition
	 *            condition to check elements' values against
	 * @return collection of removed elements
	 * @see #removeAllSatisfying(Predicate)
	 */
	public Collection<E> removeAllSatisfyingStrict(Predicate<P> condition) {
		w.lock();
		try {
			Collection<E> elements = checkConditionUnsafe(condition);
			for (E element : elements) {
				backingSet.remove(element);
			}
			size = backingSet.size();
			return elements;
		} finally {
			w.unlock();
		}
	}

	/**
	 * As {@link AggregatedSet#remove(Object)}, but additionally checks whether
	 * value of {@code elment} is satisfying {@code condition} during the time
	 * of check
	 * 
	 * @category predicate operation
	 * @param element
	 * @param condition
	 *            condition to {@code element} value against
	 * @return whether element has been removed
	 */
	public boolean removeIf(E element, Predicate<P> condition) {
		P value = getCurrentValue(element);
		if (value == null)
			return false;
		if (condition.evaluate(value))
			return remove(element);
		return false;
	}

	/**
	 * As {@link AggregatedSet#remove(Object)}, but additionally checks whether
	 * value of {@code elment} is satisfying {@code condition}. This method is
	 * <tt>strict</tt>, so it blocks the set for updates while it executes.
	 * 
	 * @category predicate operation
	 * @param element
	 * @param condition
	 *            condition to {@code element} value against
	 * @return whether element has been removed
	 */
	public boolean removeIfStrict(E element, Predicate<P> condition) {
		w.lock();
		try {
			Value<P, E> elementValue = backingSet.get(element);
			if (elementValue != null) {
				if (condition.evaluate(elementValue.getValue())) {
					backingSet.remove(element);
					size = backingSet.size();
					return true;
				}
			}
			return false;
		} finally {
			w.unlock();
		}
	}

	@Override
	public boolean retainAll(Collection<?> c) {
		boolean modified;
		w.lock();
		modified = backingSet.keySet().retainAll(c);
		size = backingSet.size();
		w.unlock();
		return modified;
	}

	/**
	 * Iterates over this set's <tt>snapshot</tt> in reverse order imposed by
	 * this set <tt>comparator</tt>
	 * 
	 * @category ordered iteration operation
	 * @return iterator
	 */
	public ValueIterator<E, P> reversedValueIterator() {
		return new DescendingIterator();
	}

	@Override
	public int size() {
		return size;
	}

	/**
	 * Iterates over this set's <tt>snapshot</tt> in order imposed by this set
	 * <tt>comparator</tt>
	 * 
	 * @category ordered iteration operation
	 * @return iterator
	 */
	public ValueIterator<E, P> valueIterator() {
		return new SortingIterator();
	}

	protected void atomicUpdate(Value<P, E> elementValue) {
		boolean stale = true;
		while (stale) {
			final P expected = elementValue.getValue();
			stale = !elementValue.compareAndSet(expected, aggregator.aggregate(
					null,
					expected));
		}
	}

	protected void atomicUpdate(Value<P, E> elementValue, P value) {
		boolean stale = true;
		while (stale) {
			final P expected = elementValue.getValue();
			final P newValue = aggregator.aggregate(value, expected);
			stale = !elementValue.compareAndSet(expected, newValue);
		}
	}

	protected Collection<E> checkConditionUnsafe(Predicate<P> condition) {
		List<E> result = new LinkedList<E>();
		Collection<Value<P, E>> elementValues = backingSet.values();
		for (Value<P, E> elementValue : elementValues) {
			if (condition.evaluate(elementValue.getValue()))
				result.add(elementValue.getElement());
		}
		return result;
	}

	protected boolean writeElementUnsafe(E e) {
		boolean elementExists;
		Value<P, E> elementValue;
		elementValue = backingSet.get(e);
		elementExists = elementValue != null;
		if (!elementExists) {
			final Value<P, E> value = new Value<P, E>(aggregator.initial(), e);
			backingSet.put(e, value);
			size = backingSet.size();
		} else {
			elementValue.set(aggregator
					.aggregate(null, elementValue.getValue()));
		}
		return elementExists;
	}

	protected boolean writeElementUnsafe(E e, P newValue) {
		boolean elementExists;
		Value<P, E> elementValue;
		elementValue = backingSet.get(e);
		elementExists = elementValue != null;
		if (!elementExists) {
			backingSet.put(e, new Value<P, E>(newValue, e));
			size = backingSet.size();
		} else {
			elementValue.set(aggregator.aggregate(newValue, elementValue
					.getValue()));
		}
		return elementExists;
	}

	static class Value<P, E> implements Comparable<Value<P, ? super E>> {

		private final E						element;

		private final AtomicReference<P>	value;

		public Value(
				P value,
				E element) {
			this.value = new AtomicReference<P>(value);
			this.element = element;
		}

		public Value(
				Value<? extends P, ? extends E> value) {
			this.value = new AtomicReference<P>(value.getValue());
			this.element = value.getElement();
		}

		public boolean compareAndSet(P expect, P update) {
			return this.value.compareAndSet(expect, update);
		}

		@Override
		public int compareTo(Value<P, ? super E> o) {
			final Comparable<P> comparable = (Comparable<P>) this.value.get();
			if (comparable == null)
				return (o.value.get() == null) ? 0 : -((Comparable<P>) o.value
						.get()).compareTo(null);
			return comparable.compareTo(o.value.get());
		}

		@Override
		public boolean equals(Object obj) {
			if (obj == null)
				return false;
			if (obj instanceof Value == false)
				return false;
			Value<P, E> other = (Value<P, E>) obj;
			return (this.element == other.element)
					|| (this.element != null && this.element
							.equals(other.element));
		}

		public E getElement() {
			return element;
		}

		public P getValue() {
			return value.get();
		}

		@Override
		public int hashCode() {
			if (this.element == null)
				return 0;
			return this.element.hashCode();
		}

		public void set(P value) {
			this.value.set(value);
		}

		@Override
		public String toString() {
			if (value == null)
				return "null";
			return value.toString();
		}
	}

	protected class ValueComparator implements Comparator<Value<P, ?>> {

		@Override
		public int compare(Value<P, ?> o1, Value<P, ?> o2) {
			return comparator.compare(o1.getValue(), o2.getValue());
		}

	}

	private class BasicIterator implements ValueIterator<E, P> {

		protected final Value<P, E>[]	array;

		protected Value<P, E>			e;

		private int						cursor;

		@SuppressWarnings("unchecked")
		public BasicIterator() {
			int i = 0;
			r.lock();
			array = new Value[backingSet.size()];
			Iterator<Value<P, E>> e = backingSet.values().iterator();
			while (e.hasNext()) {
				array[i++] = new Value(e.next());
			}
			r.unlock();
			cursor = first();
		}

		@Override
		public final boolean hasNext() {
			return cursor != last();
		}

		@Override
		public final E next() {
			E next;
			try {
				e = current(cursor);
				next = e.getElement();
			} catch (IndexOutOfBoundsException e1) {
				throw new NoSuchElementException();
			}
			cursor = forth(cursor);
			return next;
		}

		@Override
		public final void remove() {
			throw new UnsupportedOperationException();
		}

		public final P value() {
			if (e == null)
				throw new NoSuchElementException();
			return e.getValue();
		}

		protected final Value<P, E> current(int cursor) {
			return array[cursor];
		}

		protected int first() {
			return 0;
		}

		protected int forth(int cursor) {
			return cursor + 1;
		}

		protected int last() {
			return array.length;
		}

	}

	private class ConsumingDescendingIterator extends DescendingIterator {

		@Override
		protected int forth(int cursor) {
			AggregatedSet.this.remove(array[cursor].getElement());
			return super.forth(cursor);
		}

	}

	private class ConsumingIterator extends SortingIterator {

		@Override
		protected int forth(int cursor) {
			AggregatedSet.this.remove(array[cursor].getElement());
			return super.forth(cursor);
		}

	}

	private class DescendingIterator extends SortingIterator {

		@Override
		protected int first() {
			return array.length - 1;
		}

		@Override
		protected int forth(int cursor) {
			return cursor - 1;
		}

		@Override
		protected int last() {
			return -1;
		}

	}

	private class SortingIterator extends BasicIterator {

		public SortingIterator() {
			super();
			if (valueComparator != null)
				shellsort(array, valueComparator);
			else
				shellsort(array);
		}

	}

	private static final int[]	SEDGEWICKS_INCS	= new int[]
												{ 4193, 1073, 281, 77, 23, 8, 1 };

}
